iT邦幫忙

2021 iThome 鐵人賽

DAY 18
0
Software Development

程式菜鳥自學C++資料結構演算法系列 第 18

[Day18]程式菜鳥自學C++資料結構演算法 – 線性搜尋法(Linear Search)與二分搜尋法(Half-Interval Search)

  • 分享至 

  • xImage
  •  

前言:資料結構的部分已經到了尾聲,今天就要開始初探演算法的搜尋了!間天介紹的這兩個搜尋法都是始於入門款,現在就來看看吧!

搜尋的概念:

在數據集合中尋找滿足某種條件的數據元素。

平均搜尋長度(Average Search Length)
• 搜尋就是不斷將數據元素的關鍵字與待查找關鍵字進行比
較,搜尋法在成功時平均比較的次數稱作平均搜尋長度
https://ithelp.ithome.com.tw/upload/images/20211002/20140187mq34Z9gKZt.png
• Pi:搜尋第i個數據元素的機率
• Ci:搜尋該元素的過程中比較的次數

線性搜尋法:

又稱為循序搜尋法(Sequential Search),這種演算法是最簡單的,從第一筆資料到最後一筆資料進行比對,直到找到想找的資料就行。舉個簡單的例子:在書店買書的時候,若不是像漫畫小說一樣有集數的話,是不是都要一本一本掃過去才能找到像要的書?
https://ithelp.ithome.com.tw/upload/images/20211002/20140187SPRCZvoRUP.png
圖片來源:https://meet.eslite.com/Content/Images/Article/cats_20190214134118.jpg
這樣就是線性搜尋喔!只不過資料量少還可以,資料量多就越沒有效率了。

接著來實際實作看看
https://ithelp.ithome.com.tw/upload/images/20211002/201401873z88BzDxG4.png

可以看到第一個搜尋的52有成功並標示出下標(82的下標為0),而第二個搜尋的29則顯示失敗。
https://ithelp.ithome.com.tw/upload/images/20211002/20140187ifmIfU1jJC.png

二分搜尋法:

又稱為二元搜尋法(Binary Search),通常用在已經整理好(有序數組)的資料,會先把資料分成前半部和後半部,如果想要找的資料在前半部,則在把前半部分分成兩半,直到找到資料為止,這種搜尋法適合用在沒有增刪的靜態資料。
P.S.如果資料量為基數,則會無條件進位。

實際時做看看就明白怎麼操作的了。
https://ithelp.ithome.com.tw/upload/images/20211002/201401874omNZ9YwMH.png

同樣可以輸出結果。
https://ithelp.ithome.com.tw/upload/images/20211002/201401874JmGPfyfz2.png

接著來比較看看兩個搜尋法查找的次數
https://ithelp.ithome.com.tw/upload/images/20211002/20140187U1TPNuS9is.png
https://ithelp.ithome.com.tw/upload/images/20211002/20140187XldBNqAFVb.png
這樣就明顯的必較出瞭著的差異了。

最後再來分析兩個演算法的時間複雜度。(描述演算法的執行時間,時間複雜度越低代表效率越好) P.S.假設資料皆為n筆。

線性搜尋法:
	最壞情況:找到最後一筆才找資料,時間複雜度為O(n)。

    最好情況:第一筆剛好就是想找的資料,時間複雜度為O(1)。
    
二元搜尋法:
	最壞情況:每次找資料都切半,需要網前半部或後半部找,時間複雜度為O(log n)。

    最好情況:第一次切半的中間值剛好就是想找的資料,時間資料的複雜度為O(1)。

本日小結:今天介紹完了兩個基本的搜尋法,其他還有內插和費式同樣也是常見的搜尋法,不過礙於篇幅可能無法介紹到,有興趣的人可以到網路上找找相關資料,幾乎都有很詳細的解說喔o(^∀^)o

線性搜尋法

#include <vector>
#include <iostream>
using namespace std;

template<typename T, typename keyT, typename Function>
int linear_search(const vector <T>&vec,keyT key,Function fun) { //設立待搜尋的資料、關鍵字、條件的函數
	for (int i = 0; i < vec.size(); i++)
		if (fun(vec[i], key)) return i; //待搜尋的資料與關鍵字是否一樣
	return -1; //表示搜尋失敗
}
template<typename T, typename keyT>
bool Equal(T value,keyT key) { //建立比較函示判斷資料與關鍵字是否一致
	return value == key;
}

int main() {
	vector<int> v{ 82,33,64,8,19,26,52 }; 
	int ret = linear_search(v, 52, Equal<int, int>); //傳入線性表v,待搜尋的元素,比較函式及參數類型
	if (ret >= 0)std::cout << "搜尋的關鍵字:" << 52 << " 位置下標:" << ret << endl;
	ret = linear_search(v, 29, Equal<int, int>);
	if (ret >= 0)std::cout << "搜尋的關鍵字:" << 29 << " 位置下標:" << ret << endl;
	else std::cout << "搜尋失敗\n";
	return 0;
}

二元搜尋法

#include <vector>
#include <iostream>
using namespace std;

int C = 0; //計算搜尋自數次數
template<typename T, typename keyT, typename Function>
int linear_search(const vector <T>& vec, keyT key, Function fun) { //設立待搜尋的資料、關鍵字、條件的函數
	for (int i = 0; i < vec.size(); i++)
		if (fun(vec[i], key)) return i; //待搜尋的資料與關鍵字是否一樣
	return -1; //表示搜尋失敗
}
template<typename T, typename keyT>
bool Equal(T value, keyT key) { //建立比較函示判斷資料與關鍵字是否一致
	C++;
	return value == key;
}

template<typename T, typename keyT, typename Function>
int binary_search(const vector <T>& vec, keyT key, Function fun) {
	int low = 0; int high = vec.size() - 1; //定義第一個元素和最後一個元素的下標位置
	while (low <= high) { //表示存在此區間
		auto mid = (low + high) / 2;
		auto ret= fun(key,vec[mid]);
		if (ret == 0)return mid;
		else if (ret <= 0) { //說明關鍵字小於待搜尋元素
			high = mid - 1; //須更改下標
		}
		else {
			low = mid + 1;
		}
	}
	return -1;
}
template<typename T, typename keyT>
int Compare(keyT key,T value) { //同樣建立比較函式
	C++;
	return key-value;
}
int main() {
	vector<int> v{ 82,33,64,8,19,26,52 };
	C = 0;
	int ret = binary_search(v, 26, Compare<int, int>); 
	if (ret >= 0)std::cout << "搜尋的關鍵字:" << 26 << " 位置下標:" << ret << endl;
	else std::cout << "搜尋失敗\n";
	std::cout << "二分法比較次數:" << C << std::endl;

	C = 0;
	ret = linear_search(v, 26, Equal<int, int>);
	std::cout << "線性法比較次數:" << C << std::endl;
	
	return 0;
}

上一篇
[Day17]程式菜鳥自學C++資料結構演算法 – 堆積實作與應用
下一篇
[Day19]程式菜鳥自學C++資料結構演算法 – 二元搜尋樹(Binary Search Tree,BST)
系列文
程式菜鳥自學C++資料結構演算法30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言